package com.njupt.graphTheory;



import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/3 17:08
 * @Description: 拓扑排序，继续基于邻接表的广度优先遍历
 * @Version: 1.0
 */


public class CanFinish_Bfs_207 {

    /**
     * 基于图的广度优先遍历
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inEdge = new int[numCourses];

        Deque<Integer> queue = new LinkedList<>();
        //初始化图以及入度数组
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < prerequisites.length; i++) {
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
            inEdge[prerequisites[i][0]]++; //入度+1
        }

        //1、寻找入度为零的节点，将这些节点依次放入队列中
        for (int i = 0; i < inEdge.length; i++) {
            if(inEdge[i] == 0){
                queue.addLast(i);
            }
        }
        int visited = 0;
        //2、从队列中取出元素u
        while(!queue.isEmpty()){
            Integer node = queue.pollFirst();
            visited++;
            //2.1、遍历顶点为u的邻接表，对于邻接表中的每一个元素其入度剪掉1
            for (Integer v : graph.get(node)) {
                inEdge[v.intValue()]--;
                //2.2、减去1之后判断当前节点入度是否为零
                if(inEdge[v.intValue()] == 0){
                    queue.addLast(v);
                }
            }
        }

        return visited == numCourses;
    }

    public static void main(String[] args) {
//        int[][] prerequisites = {{1, 0}, {0, 1}};
        int[][] prerequisites = {{1, 0}};
        CanFinish_Bfs_207 test = new CanFinish_Bfs_207();
        System.out.println(test.canFinish(2, prerequisites));
    }
}
